package leetcode.simple._previous;

//斐波那契数列
public class FeiBo {

    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        int []arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i < n+1; i++) {
            arr[i] = (arr[i-1] % 1000000007 + arr[i-2] % 1000000007) % 1000000007;
        }

        return arr[n];
    }
}

//关于取模运算的一些公式：
/**
 * (a + b) % p = (a % p + b % p) % p
 * (a - b) % p = (a % p - b % p) % p
 * (a * b) % p = (a % p * b % p) % p
 * (a^b) % p = ((a % p)^b) % p
 *
 * 推论：
 * 若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
 * 若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
 * 若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
 * (a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)；
 *
 * 费马定理：若p是素数，a是正整数且不能被p整除，则：a^(p-1) mod p = 1 mod p
 * 推论：若p是素数，a是正整数且不能被p整除，则：a^p mod p = a mod p
 * ————————————————
 */